package PersonStu.sanqi;

import java.util.Arrays;

/**
 * @Author by KoVaVo
 * @Date 2023-01-01 17:21
 * @Desc: 给定一个数组，里面的数字表示金额，在给定一个目标值，求要组成这个目标值有多少种方式
 * [10,40,50,100] => 1000
 *
 */
public class code_23_CoinsWays {

    public static int way1(int [] nums,int aim){
        if(nums == null || nums.length == 0 || aim <= 0){
            return 0;
        }
        return process(nums,0,aim);
    }

    // arr[index....] 所有的面值，每一个面值都可以任意选择张数，组成正好rest这么多钱，方法数多少？
    private static int process(int[] arr, int index, int rest) {
        if(index == arr.length){
            return rest == 0 ? 1 : 0;
        }
        int ways = 0;
        for(int zhang = 0; zhang * arr[index] <= rest;zhang++){
            ways += process(arr,index + 1,rest - zhang * arr[index]);
        }
        return ways;
    }

    public static int wayCache(int [] arr,int aim){
        if(arr == null || arr.length == 0 || aim <= 0){
            return 0;
        }
        //构建一个动态规划，二维的
        int N = arr.length;
        int [][] dp = new int[N + 1][aim+1];
        dp[N][0] = 1;
        for(int index = N-1; index >= 0;index--){
            //从最后一行开始
            for(int rest = 0; rest <= aim; rest++){
                //从左往右开始
                int ways = 0;
                for(int zhang = 0; zhang * arr[index] <= rest;zhang++){
                    ways += dp[index + 1][rest - zhang * arr[index]];
                }
                dp[index][rest] = ways;
            }
        }
        return dp[0][aim];
    }

    public static void main(String[] args) {
        int [] nums = {10,40,50,100};
        int aim = 1000;
        int i = way1(nums, aim);
        System.out.println(i);
        System.out.println("使用动态规划");
        int i1 = wayCache(nums, aim);
        System.out.println(i1);
    }

}
